/* 

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/

// 方法一：迭代法实现子集枚举
// 时间复杂度：O(n * 2的n次方)。一共 2的n次方个状态，每种状态需要 O(n) 的时间来构造子集。
// 空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。
var subsets = function (nums) {
    const res = [];
    const len = nums.length;

    for (let mask = 0; mask < (1 << len); mask++) {
        const temp = [];
        for (let i = 0; i < len; i++) {
            if (mask & (1 << i)) {
                temp.push(nums[i]);
            }
        }
        res.push(temp);
    }

    return res;
};

// 方法二：递归法实现子集枚举
// 时间复杂度：O(n * 2的n次方)。一共 2的n次方个状态，每种状态需要 O(n) 的时间来构造子集。
// 空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。
var subsets = function (nums) {
    const res = [];
    const temp = [];
    const len = nums.length;

    const dfs = (index) => {
        if (index === len) {
            res.push(temp.slice());
            return;
        }

        temp.push(nums[index]);
        dfs(index + 1);
        temp.pop();
        dfs(index + 1);
    }

    dfs(0);

    return res;
};